BST二叉搜索树——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

#ifndef LINKEDBSTREE_H_INCLUDED
#define LINKEDBSTREE_H_INCLUDED

#include <queue>  // STL队列
#include "Entitys.h"

//========================================================================================================================================================================
//
//                                                                 BST节点结构体(BSTNode)
//
//========================================================================================================================================================================
template <typename T>
struct BSTNode {
    T data;
    BSTNode* left;
    BSTNode* right;
};

//========================================================================================================================================================================
//
//                                                                二叉搜索树结构体(LinkedBSTree)
//
//========================================================================================================================================================================
template <typename T>
struct LinkedBSTree{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        BSTNode<T>* root;          // 根节点指针
        int level;                // 用于跟踪搜索树的层次
        int depth;                // 用于跟踪搜索树的深度
        int qty;                  // 用于跟踪搜索树的节点数量

        //---------------声明私有成员函数---------------

        BSTNode<T>* createTreeNode(const T& val);// 创建新的树节点
        BSTNode<T>* findMin(BSTNode<T>* node);// 找右子树的最小节点
        BSTNode<T>* insertNode(BSTNode<T>* node, const T& val);// 插入节点（递归版本）
        BSTNode<T>* insertNodeIter(BSTNode<T>* node, const T& val);// 插入节点（迭代版本）
        BSTNode<T>* deleteNode(BSTNode<T>* node, const T& val);// 删除节点（递归版本）
        BSTNode<T>* deleteNodeIter(BSTNode<T>* node, const T& val);// 删除节点（迭代版本）
        T searchNode(BSTNode<T>* node, const T& val);// 查找节点（递归版本）
        T searchNodeIter(BSTNode<T>* node, const T& val);// 查找节点（迭代版本）
        void preOrder(BSTNode<T>* node);// 前序遍历（根 → 左 → 右）
        void inOrder(BSTNode<T>* node);// 中序遍历（左 → 根 → 右）→ 升序输出
        void postOrder(BSTNode<T>* node);// 后序遍历（左 → 右 → 根）
        void levelOrder(BSTNode<T>* node);// 层序遍历（从上到下、从左到右）
        void destroyTree(BSTNode<T>* node);// 销毁整棵树（防止内存泄漏）

    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //-------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedBSTree() {
            level = depth = qty = 0;
            root = nullptr; // 初始化为空树
        }

        BSTNode<T>* getRoot();// 获取root指针
        int isEmpty();// 判断搜索树是否为空
        int isFull();// 判断搜索树是否已满
        void insertNode(const T& val);// 插入节点
        void deleteNode(const T& val);// 删除节点
        T searchNode(const T& val);// 查找节点
        void preOrder();// 前序遍历（根 → 左 → 右）
        void inOrder();// 中序遍历（左 → 根 → 右）→ 升序输出
        void postOrder();// 后序遍历（左 → 右 → 根）
        void levelOrder();// 层序遍历（从上到下、从左到右）
        void destroyTree();// 手动销毁整棵树（防止内存泄漏）

        // 析构函数：自动销毁树，避免内存泄漏
        ~LinkedBSTree() {
            destroyTree();
        }
};

#endif // LINKEDBSTREE_H_INCLUDED

5.3 LinkedBSTree.cpp 程序代码

#include <iostream>
#include <cstdlib> 
#include "LinkedBSTree.h"

//---------------实现私有成员函数---------------

// 创建新的树节点
template <typename T>
BSTNode<T>* LinkedBSTree<T>::createTreeNode(const T& val)
{
    BSTNode<T>* node = new BSTNode<T>(); // 动态分配模板类型节点
    if (node == nullptr) { // 内存分配失败检查
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    node->data = val;
    node->left = nullptr;
    node->right = nullptr;
    qty++; // 节点数+1
    return node;
}

// 找右子树的最小节点
template <typename T>
BSTNode<T>* LinkedBSTree<T>::findMin(BSTNode<T>* node)
{
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

// 插入节点（递归版本）
template <typename T>
BSTNode<T>* LinkedBSTree<T>::insertNode(BSTNode<T>* node, const T& val)
{
    if (node == nullptr) { // 空节点，创建新节点
        qty++;
        return createTreeNode(val);
    }
    if (val < node->data) { // 小于当前节点，插入左子树
        node->left = insertNode(node->left, val);
    } else if (val > node->data) { // 大于当前节点，插入右子树
        node->right = insertNode(node->right, val);
    }
    // 等于当前节点（重复值），BST 不存储重复值，直接返回原节点
    return node;
}

// 插入节点（迭代版本）
template <typename T>
BSTNode<T>* LinkedBSTree<T>::insertNodeIter(BSTNode<T>* node, const T& val)
{
    // 处理根节点为空的特殊情况
    if (node == nullptr) {
        return createTreeNode(val);
    }

    BSTNode<T>* current = node;  // 遍历指针，从根节点开始
    BSTNode<T>* parent = nullptr; // 记录当前节点的父节点

    // 迭代查找插入位置
    while (current != nullptr) {
        parent = current; // 更新父节点为当前节点

        if (val < current->data) { // 小于当前节点，向左子树查找
            current = current->left;
        } else if (val > current->data) { // 大于当前节点，向右子树查找
            current = current->right;
        } else {
            // 找到重复值，直接返回原根节点（不插入）
            return node;
        }
    }

    // 找到插入位置，创建新节点并挂载到父节点的左/右子树
    BSTNode<T>* newNode = createTreeNode(val);
    if (val < parent->data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    // 返回原根节点（根节点未变，除非一开始就是空树）
    return node;
}

// 删除节点（递归实现）
template <typename T>
BSTNode<T>* LinkedBSTree<T>::deleteNode(BSTNode<T>* node, const T& val)
{
    if (node == nullptr) { // 未找到要删除的节点
        return nullptr;
    }

    // 1. 定位要删除的节点
    if (val < node->data) {
        node->left = deleteNode(node->left, val);
    } else if (val > node->data) {
        node->right = deleteNode(node->right, val);
    } else {
        // 2. 处理删除逻辑（分3种情况）
        // 情况1：叶子节点（无左右子树）
        if (node->left == nullptr && node->right == nullptr) {
            free(node);
            qty--;
            return nullptr;
        }
        // 情况2：只有一个子树
        else if (node->left == nullptr) { // 只有右子树
            BSTNode<T>* temp = node->right;
            free(node);
            qty--;
            return temp;
        } else if (node->right == nullptr) { // 只有左子树
            BSTNode<T>* temp = node->left;
            free(node);
            qty--;
            return temp;
        }
        // 情况3：有两个子树 → 找右子树最小节点（后继）替换
        else {
            BSTNode<T>* minRight = findMin(node->right);
            node->data = minRight->data; // 替换值
            node->right = deleteNode(node->right, minRight->data); // 删除后继节点
        }
    }
    return node;
}

// 删除节点（迭代版本）
template <typename T>
BSTNode<T>* LinkedBSTree<T>::deleteNodeIter(BSTNode<T>* node, const T& val)
{
    // 根节点为空，直接返回
    if (node == nullptr) {
        return nullptr;
    }

    BSTNode<T>* current = node;    // 遍历指针，寻找待删除节点
    BSTNode<T>* parent = nullptr;  // 待删除节点的父节点
    bool isLeftChild = false;      // 标记待删除节点是父节点的左/右孩子

    // 第一步：迭代查找待删除节点，并记录其父节点和左右孩子标记
    while (current != nullptr && current->data != val) {
        parent = current;
        if (val < current->data) {
            current = current->left;
            isLeftChild = true;
        } else {
            current = current->right;
            isLeftChild = false;
        }
    }

    // 未找到待删除节点，直接返回原根节点
    if (current == nullptr) {
        return node;
    }

    // 第二步：处理删除逻辑（分3种情况）
    BSTNode<T>* nodeToDelete = current;
    BSTNode<T>* replacement = nullptr; // 替换待删除节点的节点

    // 情况1：叶子节点（无左右子树）
    if (current->left == nullptr && current->right == nullptr) {
        replacement = nullptr;
    }
    // 情况2：只有一个子树
    else if (current->left == nullptr) { // 只有右子树
        replacement = current->right;
    } else if (current->right == nullptr) { // 只有左子树
        replacement = current->left;
    }
    // 情况3：有两个子树 → 找右子树最小节点（后继）替换
    else {
        // 迭代查找右子树的最小节点（最左节点）
        BSTNode<T>* minParent = current;
        BSTNode<T>* minNode = current->right;
        while (minNode->left != nullptr) {
            minParent = minNode;
            minNode = minNode->left;
        }

        // 替换待删除节点的值
        current->data = minNode->data;
        // 处理最小节点的替换（最小节点要么是叶子，要么只有右子树）
        if (minParent == current) { // 最小节点是待删除节点的直接右孩子
            minParent->right = minNode->right;
        } else { // 最小节点在右子树的左分支
            minParent->left = minNode->right;
        }
        // 要删除的节点变为找到的最小节点
        nodeToDelete = minNode;
        // 原待删除节点无需替换（值已更新）
        replacement = current;
    }

    // 第三步：更新父节点的子节点指针，并释放内存
    if (replacement != current) { // 非双孩子情况，需要更新父节点指针
        if (parent == nullptr) { // 待删除节点是根节点
            node = replacement;
        } else if (isLeftChild) { // 待删除节点是父节点的左孩子
            parent->left = replacement;
        } else { // 待删除节点是父节点的右孩子
            parent->right = replacement;
        }
    }

    // 释放待删除节点的内存
    free(nodeToDelete);
    qty--;

    // 返回删除后的根节点
    return node;
}

// 查找节点（递归实现）
template <typename T>
bool LinkedBSTree<T>::searchNode(BSTNode<T>* node, const T& val)
{
    if (node == nullptr) { // 未找到
        return false;
    }
    if (val == node->data) { // 找到目标值
        return true;
    } else if (val < node->data) { // 往左子树找
        return searchNode(node->left, val);
    } else { // 往右子树找
        return searchNode(node->right, val);
    }
}

// 查找节点（迭代版本）
template <typename T>
T LinkedBSTree<T>::searchNodeIter(BSTNode<T>* node, const T& val)
{
    // 初始化遍历指针，从传入的节点（通常是根节点）开始
    BSTNode<T>* current = node;

    // 迭代遍历：只要当前节点不为空，就继续查找
    while (current != nullptr) {
        if (val == current->data) {
            // 找到目标值，直接返回
            return current->data;
        } else if (val < current->data) {
            // 目标值更小，向左子树查找
            current = current->left;
        } else {
            // 目标值更大，向右子树查找
            current = current->right;
        }
    }

    // 遍历到空节点，说明未找到，返回T类型的默认值（和递归版本一致）
    return T();
}

// 前序遍历（根 → 左 → 右）
template <typename T>
void LinkedBSTree<T>::preOrder(BSTNode<T>* node)
{
    if (node == nullptr) return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

// 中序遍历（左 → 根 → 右）→ 升序输出
template <typename T>
void LinkedBSTree<T>::inOrder(BSTNode<T>* node)
{
    if (node == nullptr) return;
    inOrder(node->left);
    printf("%d ", node->data);
    inOrder(node->right);
}

// 后序遍历（左 → 右 → 根）
template <typename T>
void LinkedBSTree<T>::postOrder(BSTNode<T>* node)
{
    if (node == nullptr) return;
    postOrder(node->left);
    postOrder(node->right);
    printf("%d ", node->data);
}

// 层序遍历（从上到下、从左到右）
void LinkedBSTree<T>::levelOrder(BSTNode<T>* node)
{
    if (node == nullptr) return;

    std::queue<BSTNode<T>*> queues;
    queues.push(node); // 根节点入队

    while (!queues.empty()) {
        BSTNode<T>* curr = queues.front(); // 获取队头节点
        queues.pop();// 出队头节点
        printf("%d ", curr->data); // 输出当前节点值

        // 左子节点入队（先左后右）
        if (curr->left != NULL) {
            queues.push(curr->left);
        }
        // 右子节点入队
        if (curr->right != NULL) {
            queues.push(curr->right);
        }
    }
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedBSTree<T>::destroyTree(BSTNode<T>* node)
{
    if (node == nullptr) return;
    destroyTree(node->left);
    destroyTree(node->right);
    delete node;
}

//---------------实现公共成员函数---------------

// 获取root指针
template <typename T>
BSTNode<T>* LinkedBSTree<T>::getRoot()
{
    return root;
}

// 判断搜索树是否为空
template <typename T>
int LinkedBSTree<T>::isEmpty()
{
    return root == nullptr ? 1 : 0;
}

// 判断搜索树是否已满（链表实现永远不满，返回0）
template <typename T>
int LinkedBSTree<T>::isFull()
{
     return 0;
}

// 插入节点
template <typename T>
void LinkedBSTree<T>::insertNode(const T& val)
{
    //root = insertNode(root, val);// 插入节点（递归版本）
    root = insertNodeIter(root, val);// 插入节点（迭代版本）
}

// 删除节点
template <typename T>
void LinkedBSTree<T>::deleteNode(const T& val)
{
    //root = deleteNode(root, val);// 删除节点（递归版本）
    root = deleteNodeIter(root, val);// 删除节点（迭代版本）
}

// 查找节点
template <typename T>
bool LinkedBSTree<T>::searchNode(const T& val)
{
    //return searchNode(root,val);// 查找节点（递归版本）
    return searchNodeIter(root,val);// 查找节点（迭代版本）
}

// 前序遍历（根 → 左 → 右）
template <typename T>
void LinkedBSTree<T>::preOrder()
{
    preOrder(root);
}

// 中序遍历（左 → 根 → 右）→ 升序输出
template <typename T>
void LinkedBSTree<T>::inOrder()
{
    inOrder(root);
}

// 后序遍历（左 → 右 → 根）
template <typename T>
void LinkedBSTree<T>::postOrder()
{
    postOrder(root);
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedBSTree<T>::destroyTree()
{
    destroyTree(root);
    printf("\n===== 树内存已全部释放 =====\n");
}

// 显式实例化常用类型（避免链接错误，可选）
template class LinkedRBTree<int>;
template class LinkedRBTree<char>;
template class LinkedRBTree<float>;
template class LinkedBSTree<std::string>;
template class LinkedAVLTree<Student>; // 新增：显式实例化Student类型
template class LinkedAVLTree<StudentIndex>; // 新增：显式实例化StudentIndex类型

main.cpp 测试代码

#include "LinkedBSTree.h"
#include <iostream>
#include <string>

int main() {
    // ==================== 测试1：int类型BST搜索树 ====================
    LinkedBSTree<int> intTree;
    int intKeys[] = {10, 20, 30, 15, 25, 5, 8};
    int n = sizeof(intKeys)/sizeof(intKeys[0]);

    // 插入int节点
    std::cout << "=== Insert int keys: ";
    for (int i = 0; i < n; i++) {
        std::cout << intKeys[i] << " ";
        intTree.insertNode(intKeys[i]);
    }
    std::cout << "===" << std::endl;

    intTree.preOrder();

    // 查找测试
    int target = 31;
    if (intTree.searchNode(target)) {
        std::cout << "\nFound " << target << " in int tree!" << std::endl;
    }

    // 删除测试
    int deleteKey = 5;
    std::cout << "\n=== Delete key: " << deleteKey << " ===" << std::endl;
    intTree.deleteNode(deleteKey);
    // 前序遍历
    intTree.preOrder();

    // 销毁树（析构函数自动调用，此处显式调用演示）
    intTree.destroyTree();
    
    return 0;
}

六、注意事项

七、总结

二叉搜索树是最基础的有序二叉树结构，核心价值在于有序性和高效的查找/插入/删除：

• 中序遍历的升序特性是BST的核心标识，可直接用于有序输出；
• 链表实现的BST无容量限制，适配任意类型数据（模板化）；
• 缺点是无自平衡机制，有序插入会退化为链表，需结合AVL/红黑树优化。

本教程通过代码解析和实战示例，覆盖了BST的核心原理、关键操作实现和实际使用场景，掌握BST是学习高级平衡树（如AVL、红黑树）的基础，适用于需要高效有序数据操作的场景（如小型索引、有序集合管理）。